#include <stdlib.h>
#include <stdio.h>

#define maxSize 100
#define INF 0xffff

//存储结构
 typedef struct BTNode
{
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}*BTNode;

//先序遍历
// 递归
void preorder(BTNode T){
    if(T != NULL){
        printf("%d", T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}
//非递归
void preorderNorecursion(BTNode T){
    if(T != NULL){
        //初始化
        BTNode Stack[maxSize];
        int top = -1;
        BTNode nowNode;
        //根节点入栈
        top += 1;
        Stack[top] = T;
        while (top != -1){
            nowNode = Stack[top];
            top -= 1;
            printf("%d", nowNode->data);
            if(nowNode->rchild != NULL){
                top += 1;
                Stack[top] = nowNode->rchild;
            }
            if(nowNode->lchild != NULL){
                top += 1;
                Stack[top] = nowNode->lchild;
            }
        }
    }
}

//中序遍历
void inorder(BTNode T){
    if (T != NULL){
        inorder(T->lchild);
        printf("%d", T->data);
        inorder(T->rchild);
    }
}

void inorderNorecursion(BTNode T){
    BTNode Stack[maxSize];
    int top = -1;
    BTNode nowNode = T;
    while(top != -1 || nowNode != NULL){
        while(nowNode != NULL){
            top += 1;
            Stack[top] = nowNode;
            nowNode = nowNode->lchild;
        }
        if (top != -1){
            top -= 1;
            nowNode =  Stack[top];
            //action();
            nowNode = nowNode->rchild;
        }
    }

}

//后序遍历
void postorder(BTNode T){
    if (T != NULL){
        postorder(T->lchild);
        postorder(T->rchild);
        printf("%d", T->data);
    }
}

